public class demo2 {
    class Solution {
        int []momeory=new int[31];
        //public int fib(int n) {
        // for(int i=0;i<31;i++){
        //     momeory[i]=-1;
        //   }

        //利用递归解决  优化为记忆化搜索
        //return dfs(n);
        //}
        // public int dfs(int n){
        //     if(momeory[n]!=-1){
        //         return momeory[n];
        //     }
        //     if(n==0||n==1){
        //         momeory[n]=n;
        //         return n;
        //     }
        //     momeory[n]=dfs(n-1)+dfs(n-2);
        //     return momeory[n];
        // }
        // 利用动态规划
        int []dp=new int[31];
        public int fib(int n) {
            dp[0]=0;
            dp[1]=1;
            for(int i=2;i<31;i++){
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[n];
        }
    }
}
